import java.util.Arrays;
import java.util.Stack;

public class MyStack {
    private int[] elem;
    private int usedSize; //默认下一个放进去数据的下标，初始默认为零
    private static final int DEFAULT_CAPACITY = 10;
    public MyStack(){
        this.elem = new int[DEFAULT_CAPACITY];
    }
    public void push(int val){
        if (usedSize == elem.length){
           elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
    }
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException();
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        return oldVal;
    }
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException();
        }
        return elem[usedSize-1];
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
//    public void reversePrintList(){ //逆向打印链表中的单向链表的节点
//        Stack<ListNode> stack = new Stack<>();
//          ListNode cur = head;
//          while (cur != null){
//              stack.push(cur);
//              cur = cur.next;
//          }
//          while (!stack.isEmpty()){
//              ListNode top = stack.pop();
//              System.out.println(top.val+" ");
//          }
//        System.out.println();
//    }
    public static boolean isValid(String s){  //判断是否为有效括号
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '{' || ch == '[' || ch =='<' || ch == '('){
                stack.push(ch);
            }else {
                if (stack.empty()){
                    return false;
                }
                char top = stack.peek();
                if (ch == ')' && top == '(' || ch == '}' && top == '{' || ch == '>' && top == '<' || ch == ']' && top == '[' ){
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        if (!stack.empty()){
            return false;
        }
        return true;
    }
    public static int evalRPN(String[] tokens){
        Stack<Integer> stack = new Stack<>();
        for (String s : tokens){
            if (!isOperation(s)){
                stack.push(Integer.parseInt(s)); //将字符串变为整数
            }else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch (s){
                    case "+":
                        int ret = num1 + num2;
                        stack.push(ret);
                        break;
                    case "-":
                        int ret1 = num1 - num2;
                        stack.push(ret1);
                        break;
                    case "*":
                        int ret2 = num1 * num2;
                        stack.push(ret2);
                        break;
                    case "/":
                        int ret3 = num1 / num2;
                        stack.push(ret3);
                        break;
                }
            }
        }return stack.pop();
    }
    public static boolean isOperation(String s){
        if (s.equals("+") || s.equals("-") ||s.equals("*") ||s.equals("/")){
            return true;
        }
        return false;
    }
}
